package 九章算法DP.直方图中的最大矩形;

import java.util.Stack;

/**
 * 直方图是由排列在同一基线上的一系列矩形组成的多边形。为了简单起见，假设这些矩形的宽度相等但高度可能不同。
 * 例如，下图1给出了一个直方图，其中各个矩形的高度为3、2、5、6、1、4、4，宽度为标准1单位。
 * 当给定了一个保存所有矩形高度的数组时，如何找到其中最大的矩形。对于给定的例子，最大矩形如图阴影部分所示：
 *
 * 解法:
 * 算法思想：单调栈
 * 1、新建一个空栈，将 A[1] 压入栈中，此时 A[1] 位于栈顶。
 * 2、A[i] 与栈顶元素比较。如果A[i] 大，那么将其入栈。如果两者相等，跳过，继续下一个元素。
 * 如果A[i]小于当前栈顶元素，说明已经找到第一个位于栈顶右边的比它小的值（此时这个较小的元素还未入栈），在它的左边（在栈内就是它脚下的元素）即为第一个左边比它小的值。此时需要这样做：
 * 以栈顶元素为最小高度计算最大矩形面积，并更新现在的最大面积，宽度为左边界到右边界。
 * 弹出栈顶元素。
 * 重复第2步。
 * 3.扫描完后，一般情况下会剩下一个单调递增的堆栈，那么一个一个出栈计算面积就可以了。左边依旧还是栈顶下面那个值，右边这个时候就不存在了，最后一个栈状态的栈顶即为右边界。
 */

public class _直方图中的最大矩形 {
    public static void main(String[] args) {
        // 10
        int[] arr1 = {3, 2, 5, 6, 1, 4, 4};
        // 2*5=10
        int[] arr2 = {2, 4, 1, 3, 6, 5};
        // 3*6=18
        int[] arr3 = {4, 5, 2, 3, 7, 6, 9};

        int[] height = addZero(arr1);

        int target = maxRectangle(height);
        System.out.println(target);
    }

    public static int maxRectangle(int[] arr) {
        // 单调栈，栈中存的是数组的索引
        Stack<Integer> stack = new Stack<>();
        // 最大的矩形面积
        int sum = 0;
        // 遍历
        for (int i = 0 ; i < arr.length ; i++) {
            // 若单调栈为空或者遍历到的元素大于等于栈顶元素
            if (stack.empty() || arr[i] >= arr[stack.peek()]) {
                // 将该索引加入单调栈
                stack.push(i);
            }else {
                // 弹出栈顶元素(索引)
                int tmp = stack.pop();
                // 打擂台的方式依次替换最大值
                // arr[tmp] * (stack.empty() ? i : i - stack.peek() - 1)
                // 当前索引的矩阵高度 *
                // 若栈内不为空，则截取遍历到的当前元素到上一步pop出元素的前一个元素为止，
                // 若栈内为空，则直接取i即可，因为当栈为空的情况只发生在pop最后一号元素，此时i已经遍历到最后
                // 又pop出的最后一个矩阵高度肯定最小 故直接取i即可
                sum = Math.max(sum, arr[tmp] * (stack.empty() ? i : i - stack.peek() - 1));
                // 与i++抵消 真正操作数组中的元素(上两行是操作单调栈)
                i--;
            }
        }
        return sum;
    }
    /**
     * 将数组中末尾添加一个0(或者任意负数)，目的是用0 pop出所有栈内剩下元素
     */
    public static int[] addZero(int[] arr) {
        int[] height = new int[arr.length + 1];
        height[height.length - 1] = 0;
        for (int i = 0 ; i < arr.length ; i++) {
            height[i] = arr[i];
        }
        return height;
    }
}
